/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86185
 * Date: 2023-04-20
 * Time: 20:21
 */
/**
 *  根据一棵树的前序遍历与中序遍历构造二叉树
 */

//class Solution {
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//
//        return buildTreeChild(preorder, inorder, 0, inorder.length - 1);
//    }
//    public int preIndex;
//    private TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend) {
//        //递归出口
//        if(inbegin > inend) {
//            return null;
//        }
//        TreeNode root = new TreeNode(preorder[preIndex]);//根节点
//        int rootIndex = findIndex(inorder, inbegin, inend, preorder[preIndex]);
//        preIndex++;
//        root.left = buildTreeChild(preorder, inorder, inbegin, rootIndex - 1);
//
//        root.right = buildTreeChild(preorder, inorder, rootIndex + 1, inend);
//        return root;
//    }
//    private int findIndex(int[] inorder, int inbegin, int inend, int key){
//        for(int i = inbegin; i <= inend; i++) {
//            if(inorder[i] == key) {
//                return i;
//            }
//        }
//        return -1;
//    }
//}

/**
 * 根据一棵树的中序遍历与后序遍历构造二叉树
 */
//class Solution2 {
//    public int postIndex;
//    public TreeNode buildTree(int[] inorder, int[] postorder) {
//        postIndex = postorder.length - 1;
//        return buildTreeChild(postorder, inorder, 0, inorder.length - 1);
//    }
//
//    private TreeNode buildTreeChild(int[] postorder, int[] inorder, int inbegin, int inend) {
//        //递归出口
//        if(inbegin > inend) {
//            return null;
//        }
//        TreeNode root = new TreeNode(postorder[postIndex]);//根节点
//        int rootIndex = findIndex(inorder, inbegin, inend, postorder[postIndex]);
//        postIndex--;
//        root.right = buildTreeChild(postorder, inorder, rootIndex + 1, inend);
//        root.left = buildTreeChild(postorder, inorder, inbegin, rootIndex - 1);
//        return root;
//    }
//    private int findIndex(int[] inorder, int inbegin, int inend, int key){
//        for(int i = inbegin; i <= inend; i++) {
//            if(inorder[i] == key) {
//                return i;
//            }
//        }
//        return -1;
//    }
//}
